This invention relates to a method of and apparatus for transmitting messages over a network, and in particular, but not exclusively, is concerned with xe2x80x9ccash purchasesxe2x80x9d over a network such as the Internet.
Today, the business potential of the Internet, especially, of the world-wide-web applications, forms a new dimension in electronic commerce. It is believed that information purchases will form a very big part of the activities in the Internet electronic commerce. A typical nature of this form of commerce is to deal with a large volume of low-value payment transactions. The usual price for a few information pages can be as low as several cents. Various techniques proposed for macro payments are not suitable to be used here as transaction fees may well exceed the value of payments. Furthermore, these techniques do not preserve a proper purchaser""s anonymity which can be an essentially important feature in information purchases. On the other hand, the vast diversity of the Internet information services (e.g. web-based services) means that the subscription-based services may not be very attractive to a large number of one-off viewers. It is thus reasonable to consider facilitating information purchases over the Internet with a cash-like payment instrument.
Chaum, U.S. Pat. No. 4,759,063, discloses a blind signature technique for cash-based electronic commerce. The subject of electronic cash has thereafter been widely studied and many techniques proposed to tackle various unsolved problems. Actual systems have also been implemented for trial use. However, when considering information purchases over the Internet, these previous techniques have various limitations.
Firstly, an evident limitation in various previous off-line digital cash techniques is the high system complexity. In some of these techniques, a coin will have too big a data size to be economically used (containing a large number challenge terms for detection of cheating); some also require using complex challenge-response interactions between the payer and payee for each coin spent (a non-cash feature); others critically rely on using tamper-resistant devices (expensive smartcards with a built-in observer to monitor transactions). Systems relying on smartcards also have a limitation in quick deployment over the Internet as most home/office computers today are not readily equipped with a smartcard reader. In some of the smartcard cash techniques, the built-in observer works itself without co-working with the cardholder""s private key. Such techniques are potentially dangerous as compromising one smartcard devastates the whole system. Further, considering a fundamental principle of cryptography that a re-usable key with a limited length must have a limited lifetime, then systems using a system-wide observer also pertain to a high running cost due to the need of changing the observer in the system-wide devices from time to time.
Secondly, schemes using on-line banks, though they can prevent double spending (each coin is checked against replay during the time of payment) rather than merely detect it afterwards (yet still with a good anonymity service) are obviously not suitable for micro-payments. Here, the problem is not only in terms of economy, but also system performance. Banks are far too few compared with the vast number of small cash transactions; by processing on-line requests for such transactions, they are doomed to becoming serious system bottlenecks.
The present invention is concerned with enabling one or more of these problems to be solved, and it will be shown that an example of the invention can solve most, if not all, of these problems.
In accordance with a first aspect of the present invention, there is provided a method of transmitting a message over a network from a sender to a receiver, comprising the steps of: taking a message (Coin) to be signed by the sender; signing the message into a digital signature (e, y) of the sender, the digital signature being generated as a function of that message using public and secret signature generators (x, r) of the sender, a private key (s) of the sender, and other publicly know values (a, p, q); and transmitting the signed message over the network to the receiver; the message to be signed by the sender incorporating a first value (f(x)) which is a first predetermined function (such as a secure one-way hash function) of the sender""s public signature generator (x) into the message to be signed by the sender.
It is thus possible that the incorporation of a proper first value can be verified by a receiver of the message who requires the sender to sign the message using a public signature generator, and furthermore that if a sender signs and transmits the same message more than once, the private key of the sender can be derived from the plurality of signed messages and a relationship between the public and private signature generators.
The signature preferably includes a second value (e) which is a second predetermined function (h( )) (such as a secure one-way hash function) dependent on the first value (f(x)).
The signature preferably includes a third value (y) which is a third predetermined function of the secret signature generator (r), the second value (e), the private key (s) of the sender, and at least one (q) of the publicly known values.
The message to be signed by the sender preferably incorporates a fourth value (g(v)) which is a fourth predetermined function (g( )) (such as a secure one-way hash function) of a public key (v) of the sender.
This latter feature may be provided independently of the first aspect of the invention. Therefore, in accordance with a second aspect of the present invention, there is provided a method of transmitting a message over a network from a sender to a receiver, comprising the steps of: taking a message (Coin) to be signed by the sender; signing the message into a digital signature (e, y) of the sender, the digital signature being generated as a function of that message using public and secret signature generators (x, r) of the sender, public or private keys (v, s) of the sender, and other publicly known values (a, p, q); and transmitting the signed message over the network to the receiver; the message to be signed by the sender incorporating a fourth value (g(v)) which is a fourth predetermined function (g( )) (such as a secure one-way hash function of the public key (v) of the sender into the message to be signed by the sender.
In accordance with a third aspect of the present invention, there is provided a method of verifying a signed message received over a network, the signed message purporting to have been transmitted in accordance with the method of the first aspect of the invention, comprising the steps of: calculating an apparent public signature generator (z) of the sender using the signed message, a public key (v) of the sender and other publicly known values (a, p); calculating a fifth value (f(z)) which is the first predetermined function (f( )) of the apparent public signature generator (z); and comparing the fifth value (f(z)) with the first value (f(x)) incorporated in the received signed message.
In the case where a second value as defined above is expected in the received signed message, preferably the verifying method includes the further steps of: calculating a sixth value (e) which is the second predetermined function (h( )) of the fifth value; and comparing the sixth value (e) with the second value (e) included in the received signature.
In the case where a fourth value as defined above is expected in the received signed message, preferably the verifying method includes the further steps of: calculating a seventh value (g(v)) which is the fourth predetermined function (g( )) of a public key (v) of the sender received over the network; and comparing the seventh value (g(v)) with the fourth value (g(v)) incorporated in the signed message.
This latter feature can be provided independently of the third aspect of the invention. Therefore, in accordance with a fourth aspect of the present invention, there is provided a method of verifying the public key of the sender of a signed message received over a network, the signed message purporting to have been transmitted in accordance with a method according to the second aspect of the invention, comprising the steps of: calculating a seventh value (g((v)) which is the fourth predetermined function (g( )) of the public key (v) of the sender received over the network; and comparing the seventh value (g(v)) with the fourth value g(v) incorporated in the signed message.
The invention also encompasses apparatus which is adapted to perform any of the methods described above.